#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix)
    {
        vector<int> ret;
        int up = 0, down = matrix.size() - 1;
        int left = 0, right = matrix[0].size() - 1;

        while (true)
        {
            for (int j = left; j <= right; j++) ret.push_back(matrix[up][j]);
            if (++up > down) break;
            for (int i = up; i <= down; i++) ret.push_back(matrix[i][right]);
            if (--right < left) break;
            for (int j = right; j >= left; j--) ret.push_back(matrix[down][j]);
            if (--down < up) break;
            for (int i = down; i >= up; i--) ret.push_back(matrix[i][left]);
            if (++left > right) break;
        }

        return ret;
    }
};
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<bool> row(m), col(n);

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (matrix[i][j] == 0)
                {
                    row[i] = col[j] = true;
                }
            }
        }

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (row[i] || col[j]) matrix[i][j] = 0;
            }
        }

    }
};
class Solution {
public:
    int firstMissingPositive(vector<int>& nums)
    {
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) swap(nums[i], nums[nums[i] - 1]);
        }

        for (int i = 0; i < n; i++)
        {
            if (nums[i] != i + 1) return i + 1;
        }

        return n + 1;
    }
};
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> f(n), g(n);

        f[0] = 1, g[n - 1] = 1;
        for (int i = 1; i < n; i++) f[i] = f[i - 1] * nums[i - 1];
        for (int j = n - 2; j >= 0; j--) g[j] = g[j + 1] * nums[j + 1];

        vector<int> ans(n);
        for (int i = 0; i < n; i++) ans[i] = f[i] * g[i];

        return ans;
    }
};
class Solution {
public:
    void rotate(vector<int>& nums, int k)
    {
        int n = nums.size();
        k %= n;

        reverse(nums.begin(), nums.begin() + n - k);
        reverse(nums.begin() + n - k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals)
    {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ret;
        int left1 = intervals[0][0], right1 = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++)
        {
            int left2 = intervals[i][0], right2 = intervals[i][1];
            if (right1 >= left2)
            {
                right1 = max(right1, right2);
            }
            else
            {
                ret.push_back({ left1, right1 });
                left1 = left2;
                right1 = right2;
            }
        }
        ret.push_back({ left1, right1 });
        return ret;
    }
};
